/*
 * @Description: HuffmanTree.c
 * @author <秋落风声>
 * @addindex 2024-07-02
 * @Email <907741673@qq.com>
 * @attention： sharing content under the CC BY-NC-SA 4.0 license, please indicate the source.
 * @call: 面向离散数学编程的C语言实现---哈夫曼树。后续中文版笔记见GitHub，期末考完附上链接。
 */

//优先队列
#include"PriorityQueue.h"

HuffmanTreeNode *buildHuffmanTree(char *data, size_t freq[], int size)
{
    // 开始建哈夫曼树。

    //优先队列实现。
    PriorityQueue *pq = PQ_Create(size);

    for (int i = 0; i < size;i++)
    {
        PQ_Insert(pq, (PriorityQueueDataType)createHuffmanTreeNode(data[i], freq[i]));
    }
    HuffmanTreeNode *tmp[2] = {0};
    int count = 0;
    while(count < 2*size - 2)
    {
        tmp[count%2] = PQ_Extract(pq);
        count++;
        if(count!=0&&count%2==0)
        {
            HuffmanTreeNode *mergeNode = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode));
            mergeNode->data = '\0';
            mergeNode->left = tmp[0];
            mergeNode->right = tmp[1];
            mergeNode->weight = tmp[0]->weight + tmp[1]->weight;
            PQ_Insert(pq, (PriorityQueueDataType)mergeNode);
        }
    }
    HuffmanTreeNode *root = PQ_Extract(pq);
    PQ_Destroy(pq);//释放优先队列。
    return root;//返回哈夫曼树根结点。
}
HuffmanTreeNode *createHuffmanTreeNode(char data, size_t weight)
{
    HuffmanTreeNode *treeNode = (HuffmanTreeNode *)malloc(sizeof(HuffmanTreeNode));
    if (!treeNode)
    {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }
    treeNode->data = data;
    treeNode->weight = weight;
    treeNode->left = NULL;
    treeNode->right = NULL;
    return treeNode;
}

void HuffmanTreePrint(HuffmanTreeNode *root)
{
    //二叉树的前序遍历打印哈夫曼树。
    if(root == NULL)
        return;
    printf("%c %d\n", root->data, root->weight);
    HuffmanTreePrint(root->left);
    HuffmanTreePrint(root->right);
}
void HuffmanTreeDestroy(HuffmanTreeNode *root)
{
    //二叉树的后序遍历销毁哈夫曼树。
    if(root == NULL)
        return;
    HuffmanTreeDestroy(root->left);
    HuffmanTreeDestroy(root->right);
    free(root);
}